#include <iostream>
#include "tree.h"
using namespace std;


class cTree;
class cNode
{
        public:
      char znak;
      int waga;
      int licznik; //licznik elementow z tabeli kodow ktore nie zostaly wykorzystane ?
      bool NYT;
      cNode *Left, *Right;

      cNode(char a, int b, int c)
      {
        znak=a;
        waga = b;
        licznik = c;
        Left=0;
        Right=0;
      }
    friend class cTree;
};
int dupa_test;
//---------------------------------------------------
class cTree
{
        cNode *head;
        int iRozmiar_alfabetu;
        void delete_node(cNode *);
        void add_node(cNode *&,char);
        void inorder(cNode *);
        void postorder(cNode *);
        void preorder(cNode *);
        int size(cNode *);
    public:
        cTree(int rozmiar)
        {
            head=NULL;
            iRozmiar_alfabetu = rozmiar;
            add_to_tree('0');
        }
        ~cTree(){
            delete_node(head);}
        void add_to_tree(char znak){add_node(head,znak);}

        void InOrder(){inorder(head);}
        void PostOrder(){postorder(head);}
        void PreOrder(){preorder(head);}
        void swap_children(cNode *);    //zamienia ze sobą potomstwo korzenia wsk1
        void swap_int(cNode *);      //zamienia wartości liczków
        int Size(){return size(head)-1;}
        bool search(cNode *,char );
        cNode *get_head(){return head;}

        cNode *szukaj_wierzcholka(cNode *,char ); // zwraca wskaźnik na szukany wierzchołek lub NULL
        void uaktualnij_wagi_2(cNode *);     //funkcja aktualizująca wagi drzewa huffmana
        cNode *szukaj_NYT(cNode *);      //zwraca wskaźnik na NYT
};
//---------------------------------------------------
void cTree::add_node(cNode *&node, char znak)    //dodaje wierzcholek do drzewa
{
  if ( node==NULL ){
      node=new cNode('g', 0, iRozmiar_alfabetu--);
      return ;
  }
  if(!search(get_head(), znak))
    {
        cNode *temp;
        temp = szukaj_NYT(get_head());
        temp->Left = new cNode('g', 0, iRozmiar_alfabetu--);
        temp->Right = new cNode(znak, 1, iRozmiar_alfabetu--);
        temp->waga = temp->Left->waga + temp->Right->waga;
    }
    else
    {
        cNode *temp;
        temp = szukaj_wierzcholka(get_head(), znak);
        temp->waga++;
    }
    uaktualnij_wagi_2(get_head());
}
//---------------------------------------------------
void cTree::uaktualnij_wagi_2(cNode *wsk){
    if(wsk->waga != 0){
    if(wsk->Left->znak == 'g' && wsk->Left->waga != 0)
        uaktualnij_wagi_2(wsk->Left);
    if(wsk->Right->znak == 'g' && wsk->Right->waga != 0)
        uaktualnij_wagi_2(wsk->Right);

    wsk->waga=wsk->Left->waga + wsk->Right->waga;
    if(wsk->Left->waga > wsk->Right->waga)
        swap_children(wsk);
    if (wsk->Left->licznik > wsk->Right->licznik)
        swap_int(wsk);
    }
    return ;
}
//---------------------------------------------------
void cTree::swap_int(cNode *wsk)
{
    int temp=wsk->Left->licznik;
    wsk->Left->licznik=wsk->Right->licznik;
    wsk->Right->licznik=temp;

}
//---------------------------------------------------
void cTree::swap_children(cNode *wsk)
{
    cNode *temp = wsk->Left;
    wsk->Left = wsk->Right;
    wsk->Right = temp;
}
//---------------------------------------------------
cNode *cTree::szukaj_NYT(cNode *wsk)
{
    if(wsk->waga==0) return wsk;
    if (wsk->Left->znak=='g' ) return szukaj_NYT(wsk->Left);
    if(wsk->Right->znak=='g' ) return szukaj_NYT(wsk->Right);
    return 0;

}
//---------------------------------------------------
cNode *cTree::szukaj_wierzcholka(cNode *wsk,char znak)
{
    if(wsk->waga != 0){
    if(wsk->Left->znak == znak)
        return wsk->Left;
    if(wsk->Right->znak == znak)
        return wsk->Right;
    if(wsk->Left->znak == 'g' && wsk->Left->waga !=0)
        return szukaj_wierzcholka(wsk->Left, znak);
    if(wsk->Right->znak == 'g' && wsk->Right->waga !=0)
        return szukaj_wierzcholka(wsk->Right, znak);
}
}
//-----------------------------------------------------
void cTree::delete_node(cNode *ogniwo)  //usuwa poddrzewo o korzeniu ogniwo
{
  if (ogniwo != NULL)
    {
    cNode * lewy=ogniwo->Left;
    cNode * prawy=ogniwo->Right;
    delete ogniwo;
    ogniwo = NULL;
    delete_node(lewy);
    delete_node(prawy);
    }
}

void cTree::inorder(cNode *node)    //przegladanie w porzatku inorder
{
    if (node==NULL) return;
    if(node->Left)inorder(node->Left);
    cout <<node->znak<< " licznik: " <<node->licznik<< " waga: " <<node->waga<<" \n";
    if(node->Right)inorder(node->Right);
    cout <<"========================\n";


}
//---------------------------------------------------
void cTree::preorder(cNode *node)   //przegladanie w porzatku preorder
{
    if (node==NULL) return;
    cout <<node->znak<<" ";
    preorder(node->Left);
    preorder(node->Right);
}
//---------------------------------------------------
void cTree::postorder(cNode *node)  //przegladanie w porzatku postorder
{
    if (node==NULL) return;
    preorder(node->Left);
    cout <<node->znak<<" ";
    preorder(node->Right);
}
//---------------------------------------------------
int cTree::size(cNode *node)    //zwraca rozmiar drzewa
{
    if (node==NULL) return 1;
    return size(node->Left)+size(node->Right);
}
//---------------------------------------------------
bool cTree::search(cNode *wsk,char znak)    //szuka elementu znak w drzewie
{
    if(wsk->waga != 0)
    {
        if(wsk->Left->znak == znak)
            return 1;
        if(wsk->Right->znak == znak)
            return 1;
        if(wsk->Left->znak == 'g' && wsk->Left->waga !=0)
            return search(wsk->Left, znak);
        if(wsk->Right->znak == 'g' && wsk->Right->waga !=0)
            return search(wsk->Right, znak);
    }
    return 0;
}
